Apprentissage par différences temporelles (Temporal-Difference - TD)

5. Méthode Sarsa : Contrôle de type On-Policy

Nous allons maintenant nous intéresser à l'utilisation des méthodes par différences temporelles dans le but de construire des stratégies optimales. Comme d'habitude, nous allons suivre les idées proposées par les méthodes d'itérations des stratégies généralisées (GPI), en utilisant les méthodes TD pour l'évaluation et la prédiction. Comme pour les méthodes de Monte-Carlo nous allons être confronté au problème de balance entre l'exploitation et l'exploration. Ici nous nous intéressons à une méthode de type On-Policy.

5.2. Exemple d'illustration

Prenons l'exemple de l'environnement Frozen-Lake. Considérons que l'agent se trouve sur l'état (4,2) et se déplace vers l'état (4,3) en suivant la stratégie $\varepsilon$-greedy:

Voyons comment est calculée la nouvelle valeur de l'état (4,2) suite à cette action:

Ce processus est ensuite répété tout au long de l'épisode.

On peut montrer que l'algorithme Sarsa converge vers la stratégie optimale (avec une probabilité de 1) tant que toutes les paires d'état-action de l'environnement sont visitées une infinité de fois.

Une stratégie qui permet d'explorer l'ensemble des possibilités est par exemple la stratégie $\varepsilon$-greedy. Dans la plupart des cas, une valeur de $\varepsilon=0.1$ est un bon choix. Une valeur trop haute de $\varepsilon$ va entrainer une convergence plus lente car il y aura davantage d'explorations. À l'inverse, une valeur trop petite empêchera l'agent d'explorer l'environnement.